//
// Created by 123 on 2024/4/5.
//
//
// Created by 123 on 2024/4/5.
//
/**
 * 堆排序
 *      首先建立大根堆
 *
 *
 *     更新 n 轮最小位置
 *     即成
 *
 *      O(nlog n)
 */
#include <iostream>

using namespace std;

#define MaxSize 100

typedef struct Array {
    int data[MaxSize];
    int length;
} Array, *Arr;

Array *initArray(int arr[], int len);

void swap(int &a, int &b);



void merge_sort(Arr &arr);
void merge_sort_ope(Arr &arr,int low,int high);

void merge(Arr  &arr,int low ,int mid ,int high);

int main() {
    int a[10]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    Arr arr = initArray(a, 10);
    merge_sort(arr);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
}

void merge_sort(Arr &arr) {
    merge_sort_ope(arr,0,arr->length-1);

}
void merge_sort_ope(Arr &arr,int low,int high){
    if(low>=high)
        return;
    int mid=(low+high)/2;
    merge_sort_ope(arr,low,mid);
    merge_sort_ope(arr,mid+1,high);
    merge(arr,low,mid,high);
}
void merge(Arr  &arr,int low ,int mid ,int high){
    int temp[arr->length];
    for (int i = 0; i < arr->length; ++i) {
        temp[i]=arr->data[i];
    }
    int l_index=low;
    int h_index=mid+1;
    while (l_index<=mid&&h_index<=high){
        if(temp[l_index]<=temp[h_index])
            arr->data[low++]=temp[l_index++];
        else
            arr->data[low++]=temp[h_index++];
    }
    while (l_index<=mid)
        arr->data[low++]=temp[l_index++];
    while (h_index<=high)
        arr->data[low++]=temp[h_index++];

}



Array *initArray(int arr[], int len) {
    Arr array = (Array *) malloc(sizeof(Array));
    for (int i = 0; i < len; ++i) {
        array->data[i] = arr[i];
    }
    array->length = len;
    return array;
}

void swap(int &a, int &b) {
    int turn = a;
    a = b;
    b = turn;
}
